import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/11 14:27
 * @description
 */
public class Solution {
    public static void main(String[] args) {

    }
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        ArrayList<Interval> list = new ArrayList<>();
        if (intervals.size() == 0) {
            return list;
        }
        // 按区间左端点升序
        Collections.sort(intervals, (a, b) -> a.start - b.start);
        int left = intervals.get(0).start, right = intervals.get(0).end;
        if (intervals.size() == 1) {
            list.add(new Interval(left, right));
            return list;
        }
        for (int i = 1; i < intervals.size(); i++) {
            Interval t = intervals.get(i);
            if (t.start <= right) {
                right  = Math.max(t.end, right);
            }else {
                list.add(new Interval(left, right));
                left = t.start;
                right = t.end;
            }
        }
        list.add(new Interval(left, right));
        Collections.sort(list, (a, b) -> a.start - b.start);
        return list;
    }
}

class Interval{
    int start;
    int end;
    public Interval() {
        start = 0;
        end = 0;
    }
    Interval(int s, int e) {
        this.start = s;
        this.end = e;
    }
}